TNotes.leetcode

Appearance

⏰0853. 车队【中等】

0853. 车队【中等】 ​

1. 📝 题目描述 ​

在一条单行道上，有 n 辆车开往同一目的地。目的地是几英里以外的 target。

给定两个整数数组 position 和 speed，长度都是 n，其中 position[i] 是第 i 辆车的位置， speed[i] 是第 i 辆车的速度(单位是英里/小时)。

一辆车永远不会超过前面的另一辆车，但它可以追上去，并以较慢车的速度在另一辆车旁边行驶。

车队 是指并排行驶的一辆或几辆汽车。车队的速度是车队中 最慢 的车的速度。

即便一辆车在 target 才赶上了一个车队，它们仍然会被视作是同一个车队。

返回到达目的地的车队数量。

示例 1：

txt
输入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
输出：3
  • 解释：
    • 从 10（速度为 2）和 8（速度为 4）开始的车会组成一个车队，它们在 12 相遇。车队在 target 形成。
    • 从 0（速度为 1）开始的车不会追上其它任何车，所以它自己是一个车队。
    • 从 5（速度为 1） 和 3（速度为 3）开始的车组成一个车队，在 6 相遇。车队以速度 1 移动直到它到达 target。

示例 2：

txt
输入：target = 10, position = [3], speed = [3]
输出：1
解释：只有一辆车，因此只有一个车队。

示例 3：

txt
输入：target = 100, position = [0,2,4], speed = [4,2,1]
输出：1
  • 解释：
    • 从 0（速度为 4） 和 2（速度为 2）开始的车组成一个车队，在 4 相遇。从 4 开始的车（速度为 1）移动到了 5。
    • 然后，在 4（速度为 2）的车队和在 5（速度为 1）的车成为一个车队，在 6 相遇。车队以速度 1 移动直到它到达 target。

提示：

  • n == position.length == speed.length
  • 1 <= n <= 10^5
  • 0 < target <= 10^6
  • 0 <= position[i] < target
  • position 中每个值都 不同
  • 0 < speed[i] <= 10^6

2. 🎯 s.1 - 排序 ​

c
int cmp(const void* a, const void* b) {
    double* pa = (double*)a, *pb = (double*)b;
    return pb[0] > pa[0] ? 1 : -1;
}

int carFleet(int target, int* position, int positionSize, int* speed, int speedSize) {
    int n = positionSize;
    double (*cars)[2] = malloc(sizeof(double[2]) * n);
    for (int i = 0; i < n; i++) {
        cars[i][0] = position[i];
        cars[i][1] = (double)(target - position[i]) / speed[i];
    }
    qsort(cars, n, sizeof(double[2]), cmp);
    int fleets = 0;
    double maxTime = 0;
    for (int i = 0; i < n; i++) {
        if (cars[i][1] > maxTime) { fleets++; maxTime = cars[i][1]; }
    }
    free(cars);
    return fleets;
}
js
/**
 * @param {number} target
 * @param {number[]} position
 * @param {number[]} speed
 * @return {number}
 */
var carFleet = function (target, position, speed) {
  const cars = position.map((p, i) => [p, (target - p) / speed[i]])
  cars.sort((a, b) => b[0] - a[0])
  let fleets = 0,
    maxTime = 0
  for (const [_, time] of cars) {
    if (time > maxTime) {
      fleets++
      maxTime = time
    }
  }
  return fleets
}
py
class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)
        fleets = 0
        max_time = 0
        for p, s in cars:
            t = (target - p) / s
            if t > max_time:
                fleets += 1
                max_time = t
        return fleets
  • 时间复杂度：O(nlog⁡n)，其中 n 是车的数量
  • 空间复杂度：O(n)

算法思路：

  • 按位置降序排列，计算每辆车到达终点的时间
  • 从最前的车开始遍历，若当前车到达时间超过前方最大时间，则形成新车队